/**
 * Refactored java code by Illya Havsiyevych
 * http://illya-keeplearning.blogspot.com/search/label/suffix%20tree
 * Originally based on Mark Nelson's C++ implementation of Ukkonen's algorithm
 * http://marknelson.us/1996/08/01/suffix-trees/
 *
 * Changes made to suit Trellis Algorithm by Alexandros Konstantinakis - Karmis
 */

import java.util.*;
import org.apache.hadoop.io.Writable;
import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
import org.apache.hadoop.io.WritableUtils;
import org.apache.hadoop.io.WritableComparator;
import org.apache.hadoop.io.WritableComparable;
import org.apache.hadoop.io.Text;



//MAX FILE 2GB

public class SuffixTree implements WritableComparable <SuffixTree> {
  private int globalOffset;
//  private int internalOffset;
  private String text;
//  public int intprefix;
//  private int fileLength;

  private String prefix;
  private Node root;
  private int nodesCount; //number of nodes in here
  private int leavesCount;//the number of leaves this suffixTree should have

  public void readFields(DataInput in) throws IOException {
    globalOffset = in.readInt();
//    internalOffset = in.readInt();
//    intprefix = in.readInt();
    nodesCount = WritableUtils.readVInt(in);
    leavesCount = WritableUtils.readVInt(in);
//    fileLength = WritableUtils.readVInt(in);
//    text = WritableUtils.readString(in);
    prefix = WritableUtils.readString(in);
//    globalOffset = in.readLong();
   
    Node rootNode = new Node();
    rootNode.readFields(in);
    root = rootNode;

    //taking care of this, although the merger will change them. however the final output needs it!
/*    Queue<Node> queue = new LinkedList<Node>();
    queue.add(getRootNode());
    while (!queue.isEmpty()) {
      Node node = queue.remove();


      node.setSuffixTree(this);


      for (Edge edge : node.getEdges()) {
        if (edge.getEndNode() != null)
          queue.add(edge.getEndNode());
      }
    }*/
  }

  public void write(DataOutput out) throws IOException {
    out.writeInt(globalOffset);
//    out.writeInt(internalOffset);
//    out.writeInt(Integer.parseInt(prefix));
    WritableUtils.writeVInt(out, nodesCount);
    WritableUtils.writeVInt(out, leavesCount);
//    WritableUtils.writeVInt(out, fileLength);
//    WritableUtils.writeString(out,text.substring(internalOffset));//we are only saving the part that matters
    WritableUtils.writeString(out,prefix);
//    out.writeLong(globalOffset);

    root.write(out);
  }
  
  public SuffixTree() {
    //root = new Node(this, null);
    root = new Node();
  }

  public void populate(Node mainNode, Node tmpNode) {
    for (char key: tmpNode.getKeys()) {
      Edge tmpEdge = tmpNode.findEdge(key);
      Edge newEdge = new Edge(tmpEdge.getBeginIndex(), tmpEdge.getCharIndex(), tmpEdge.getEndIndex(), mainNode, getNewNodeNumber());
      newEdge.insert();
      populate(newEdge.getEndNode(), tmpEdge.getEndNode());
    }
  }

  public SuffixTree (SuffixTree tmp) {
      this.globalOffset = tmp.getGlobalOffset();
      this.nodesCount = tmp.getNodesCount();
      this.leavesCount = tmp.getLeavesCount();
      this.prefix = tmp.getPrefix();

      root = new Node();
      populate(root, tmp.getRootNode());
  }

  public SuffixTree(int globalOffset) {
    root = new Node();
    this.globalOffset = globalOffset;
  }

/*  @Override
  public boolean equals(SuffixTree that) {
    if ((this.getPrefix() == that.getPrefix()) && (this.getGlobalOffset() == that.getGlobalOffset()) && (this.getInternalOffset() == that.getInternalOffset()))
      return true;
    return false;
  }*/

/*  @Override
  public int hashCode() {
    return (this.getPrefix().hashCode() ^ this.getGlobalOffset() ^ this.getGlobalOffset());
  }

  public void clearFields() {
    
  }

  public static SuffixTree read(DataInput in) throws IOException {
    SuffixTree sf = new SuffixTree();
    sf.readFields(in);
    return sf;
  }*/


/*  public SuffixTree(int globalOffset, int internalOffset, int fileLength, String prefix, Node root, int nodesCount, int leavesCount) {
    this.globalOffset = globalOffset;
    this.internalOffset = internalOffset;
    this.fileLength = fileLength;
    this.prefix = prefix;
    this.root = new Node(root, 1);
    this.nodesCount = nodesCount;
    this.leavesCount = leavesCount;
  }*/

//  public SuffixTree(String text, String prefix, long globalOffset, long fileLength) {//Change this to Text???
  public SuffixTree(Text text, int max, String prefix, long globalOffset, long fileLength) {//Change this to Text???
    nodesCount = 0;
    leavesCount = 0;
//    this.text = text;
    this.prefix = prefix;
    this.globalOffset = (int) globalOffset;
//    this.fileLength = (int) fileLength;
 //   this.internalOffset = -1;
//    root = new Node(this, null);
    root = new Node(this.getNewNodeNumber());

    Suffix active = new Suffix(root, 0, -1);

    int i = 0;
    i = text.find(prefix);//position in text
    while ((i != -1) && (i <= text.getLength() - max + prefix.length())) {
      leavesCount++;
      active.setBeginIndex(i);
      active.setEndIndex(i-1);
      active.setOriginNode(root);
      addPrefix(active, (int) fileLength);
      i = text.find(prefix,i+1);
    }


/*    while (i<text.length()) {
      if (prefix.length()+i<=text.length() && prefix.equals(text.substring(i,i+prefix.length()))) { //iff prefix is in bounds and is found at this character in the text
//        if (internalOffset == -1)
//          internalOffset = i;
        leavesCount++;
        active.setBeginIndex(i);
        active.setEndIndex(i-1);
        active.setOriginNode(root);
//        System.out.println("adding prefix: " + prefix + " at " + i);
        addPrefix(active, (int) fileLength);
        //dumpEdges();
      }
      i++;
    }*/
    //System.out.println("internal offset is " + internalOffset);
  }

  /**
   * Adds a prefix to the SuffixTree.
   * This is only called when a prefix is found in the given input
   * @param  suffix A Suffix describing the new prefix
   */
  private void addPrefix(Suffix active, int fileLength) {
    Node lastParentNode = null;
    Node parentNode;
    Edge edge;
    parentNode = active.getOriginNode();
    edge = parentNode.findEdge(text.charAt(active.getBeginIndex()));
    if (edge == null) { //Explicit, the new prefix doesn't start inside a present Edge
      Edge newEdge = new Edge(active.getBeginIndex()+globalOffset, text.charAt(active.getBeginIndex()), fileLength, parentNode, getNewNodeNumber()); //new Edge from currentPosition (global) to EndOfFile !!!
      newEdge.insert();
    } else { //Implicit, the new prefix starts inside a present Edge
      boolean found = false;
      while (!found) {//lookahead 1 char
        for (int i = 0; (i < edge.getSpan()) && (!found); i++) { //gia ola ta shmeia tou edge
          active.incEndIndex();
          if (text.charAt(edge.getBeginIndex() + active.getSpan() + 1 - globalOffset) != text.charAt(active.getEndIndex()+1)) {//if the next character differs
            int a = edge.getBeginIndex() + active.getSpan() + 1 - globalOffset;
 //           System.out.println("pos: " + a + " char: " + text.charAt(a));
            parentNode = edge.splitEdge(active, text.charAt(a), getNewNodeNumber());
            found = true;
          }
        }
        if (!found) {
          active.setOriginNode(edge.getEndNode());
          active.setBeginIndex(active.getBeginIndex() + edge.getSpan() + 1);
          active.incEndIndex();
          parentNode = active.getOriginNode();
          edge = edge.getEndNode().findEdge(text.charAt(active.getBeginIndex()));
          if (edge == null) {
            break;
          }
        }
      }
      active.incEndIndex();
//      System.out.println("pos: " + (active.getEndIndex()) + " char: " + text.charAt(active.getEndIndex()));
      Edge newEdge2 = new Edge(active.getEndIndex() + globalOffset, 
                              text.charAt(active.getEndIndex()),
                              fileLength,
                              parentNode, getNewNodeNumber()); //ftiaxnw ena neo edge to opoio tha einai to suffix apo tin thesi pou eimai mexri to telos
      newEdge2.insert();
    }
  }

  public int getNewNodeNumber() {
    return nodesCount++;
  }

  public String getText() {
    return text;
  }

  public String getPrefix() {
    return prefix;
  }

  public int getGlobalOffset() {//LOL
    return globalOffset;
  }
  
  public void setGlobalOffset(int go) {//LOL
    this.globalOffset=go;
  }
  
/*  public int getFileLength() {
    return fileLength;
  }
  
  public void setFileLength(int fl) {
    this.fileLength = fl;
  }*/

/*  public int getInternalOffset() {//LOL
    return internalOffset;
  }

  public void setInternalOffset(int io) {//LOL
    this.internalOffset=io;
  }*/

  public Node getRootNode() {
    return root;
  }

  public int getLeavesCount() {
    return leavesCount;
  }
  public void setLeavesCount(int lc) {
    this.leavesCount = lc;
  }
  public int getNodesCount() {
    return nodesCount;
  }

  /**
   * Tests the SuffixTree for coherence.
   * In any given SuffixTree, the number of leaves must be equal to the number of appearances of the given prefix in the Text.
   * @return True if the SuffixTree is coherent
   */
  public boolean test() {
    int counter = 0;
    Queue<Node> queue = new LinkedList<Node>();
    queue.add(getRootNode());

    while (!queue.isEmpty()) {
      Node node = queue.remove();
      for (Edge edge : node.getEdges()) {
        //        if (edge.getEndNode().getSuffixNode() == null) {//NOT ANYMOAR
        //        if (edge.getEndIndex() == fileLength) {
        if (edge.getEndNode().getSize() == 0) {
          counter++;
        } else {
          queue.add(edge.getEndNode());
        }
      }
    }

      if (getLeavesCount() != counter)
        System.out.println("leavesCount = " + getLeavesCount() + " != " + counter + " = counter");
      return(getLeavesCount() == counter);
  }

/*  public void dumpEdges() {
//    System.out.println("Edge \tStart \t CharIndex \tEnd \tSuf \tFirst \tLast \tString");
    System.out.println("Edge \tStart \t CharIndex \tEnd \tFirst \tLast \tString");
    Queue<Node> queue = new LinkedList<Node>();

    queue.add(getRootNode());
    while (!queue.isEmpty()) {
      Node node = queue.remove();
      for (Edge edge : node.getEdges()) {
//        Node suffixNode = edge.getEndNode().getSuffixNode();//WHY keep this since it's going to get deleted anyway?
        System.out.print(edge + " " +
            "\t" + edge.getStartNode() + " " +
            "\t\t" + edge.getCharIndex() + " " +
            "\t" + edge.getEndNode() + " " +
//            "\t" + ((suffixNode == null) ? "-1" : suffixNode) + " " +
            "\t" + edge.getBeginIndex() + " " +
            "\t" + edge.getEndIndex() + " " +
            "\t" + ((edge.getEndNode() == null) ? text.substring(edge.getBeginIndex()-globalOffset): text.substring(edge.getBeginIndex()-globalOffset, edge.getEndIndex()-globalOffset+1)));
//        for (int l = edge.getBeginIndex(); l <= edge.getEndIndex(); l++)
//          System.out.print(getText().charAt(l));
        System.out.println();

        if (edge.getEndNode() != null)
          queue.add(edge.getEndNode());
      }
    }
  }*/
  public void dumpEdges2() {
//    System.out.println("Edge \tStart \t CharIndex \tEnd \tSuf \tFirst \tLast \tGlobalOffset \tInternalOffset \tString");
    System.out.println("Edge \tStart \t CharIndex \tEnd \tFirst \tLast \tGlobalOffset");
    Queue<Node> queue = new LinkedList<Node>();

    queue.add(getRootNode());
    
    try {
//      Braf braf = new Braf("./input_sequence/input", "r", 128*1024*1024);
      while (!queue.isEmpty()) {
        Node node = queue.remove();
        for (Edge edge : node.getEdges()) {
//          Node suffixNode = edge.getEndNode().getSuffixNode();//WHY keep this since it's going to get deleted anyway?
//          System.out.println(edge.getSpan());
//          byte[] text = new byte[edge.getSpan()+1];
//          braf.seek(edge.getBeginIndex());
//          braf.read(text, 0, edge.getSpan()+1);
          System.out.print(edge + " " +
              "\t" + edge.getStartNode() + " " +
              "\t\t" + edge.getCharIndex() + " " +
              "\t" + edge.getEndNode() + " " +
//              "\t" + ((suffixNode == null) ? "-1" : suffixNode) + " " +
              "\t" + edge.getBeginIndex() + " " +
              "\t" + edge.getEndIndex() + " "
//              "\t" + edge.getStartNode().getSuffixTree().getGlobalOffset()
//              "\t\t" + edge.getStartNode().getSuffixTree().getInternalOffset() +
//              "\t\t" + new String(text)
             );
          //        for (int l = edge.getBeginIndex(); l <= edge.getEndIndex(); l++)
          //          System.out.print(getText().charAt(l));
          System.out.println();

          if (edge.getEndNode() != null)
            queue.add(edge.getEndNode());
        }
      }
    } catch (Exception e) {
      System.out.println("Exception " + e.getMessage());
    }
  }

/*  public static class SuffixTreeComparator extends WritableComparator {
    public SuffixTreeComparator() {
      super(SuffixTree.class);
    }   */
    
    //Don't use this
    public int compareTo(SuffixTree other) {
      int gothis = this.getGlobalOffset();
      int goother = other.getGlobalOffset();

      if (gothis<goother) {
        return -1; 
      } else if (gothis > goother) {
        return 1;
      } else {
        return 0;
      }   
    } 
/*  }
  
  static {                                        // register this comparator
    WritableComparator.define(SuffixTree.class, new SuffixTreeComparator());
  }
*/

  
    public static class GroupingComparator extends WritableComparator {
      public GroupingComparator() {
        super(SuffixTree.class);
      }
      public int compare (byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {
        try {
          for (int i =0; i<20; i++)
            System.out.print(i + ": " + readInt(b1,i) + " ");
          System.out.println();
          int thisp = readInt(b1, 15); //SURE!
          int thatp = readInt(b2, 15);
          if (thisp < thatp) {
            System.out.println("comparator says: " + thisp + " < " + thatp);
            return -1;
          } else if (thisp > thatp) {
            System.out.println("comparator says: " + thisp + " > " + thatp);
            return 1;
          } else {
            System.out.println("comparator says: " + thisp + " = " + thatp);
            return 0;
          }
        } catch (ArrayIndexOutOfBoundsException e) {
            System.out.println("comparator says error");
/*          for (int i =0; i<10; i++)
            System.out.print(i + ": " + readInt(b1,i) + " ");
          System.out.println();
          for (int i =0; i<10; i++)
            System.out.print(i + ": " + readInt(b2,i) + " ");
          System.out.println();
          System.out.println();*/
          return(0);
        }
      }
    }
    
    static {
      // register this comparator
      WritableComparator.define(SuffixTree.class, new GroupingComparator());
    }


    /** A WritableComparator optimized for Text keys. */
    public static class Comparator extends WritableComparator {
      public Comparator() {
        super(SuffixTree.class);
      }

      public int compare (byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {
/*        String thisprefix = WritableUtils.readString(b1);
        String thisprefix = WritableUtils.readString(b2);*/
/*        int thisint = readInt(b1,s1);
        int thatint = readInt(b2,s2);
        System.out.println("this: " + thisint + " that " + thatint); 
        return 0;*/



        try {
          int thisgo = readInt(b1, 7); //SURE!
          int thatgo = readInt(b2, 7);
/*          int thisio = readInt(b1, 9); //NOT SURE!
          int thatio = readInt(b2, 9);*/

          for (int i =0; i<20; i++)
            System.out.print("|" + i + "| " + readInt(b1,i) + " " + readInt(b2,i));
          System.out.println();
          if (thisgo<thatgo) {
//                      System.out.println("comparator says: " + thisgo + " < " + thatgo);
            return -1;
          } else if (thisgo>thatgo) {
//                      System.out.println("comparator says: " + thisgo + " > " + thatgo);
            return 1;
          } else {
/*            if (thisio<thatio) {
//                          System.out.println("comparator says: " + thisgo + " = " + thatgo + " and " + thisio + " < " + thatio);
              return -1;
            } else if (thisio>thatio) {
//                          System.out.println("comparator says: " + thisgo + " = " + thatgo + " and " + thisio + " > " + thatio);
              return 1;
            } else {
//                          System.out.println("comparator says: " + thisgo + " = " + thatgo + " and " + thisio + " = " + thatio);
             */ return 0;
            }
          
        } catch (ArrayIndexOutOfBoundsException e) {
         // int n1 = WritableUtils.decodeVIntSize(b1[s1]);
         // int n2 = WritableUtils.decodeVIntSize(b2[s2]);
          //return compareBytes(b1, s1+n1, l1-n1, b2, s2+n2, l2-n2);
          return 0;

//          return Text.Comparator.compare(b1, s1, l1, b2, s2, l2);
/*          System.out.println("ERROR in SF comparator");
          for (int i =0; i<7; i++)
            System.out.print("|" + i + "| " + readInt(b1,i) + " " + readInt(b2,i));
          System.out.println();
          return(0);*/
        }
      }
    }

    static {
      // register this comparator
      WritableComparator.define(SuffixTree.class, new Comparator());
    }



}
